#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
const int N = 2e5 + 5;

ll n, ans;
ll mul(ll a, ll b, ll mod) { return (__int128_t)a * b % mod; }
ll fastpow(ll b, ll p, ll mod) {
  ll res = 1;
  while (p) {
    if (p & 1) res = mul(res, b, mod);
    b = mul(b, b, mod);
    p >>= 1;
  }
  return res;
}
ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); }
ll miller_rabin(ll p) {
  if (p < 2) return false;
  if (p == 2 || p == 3) return true;
  ll d = p - 1, r = 0;
  while (!(d & 1)) d >>= 1, r++;
  rep(k, 1, 10) {
    ll a = rand() % (p - 2) + 2;
    ll x = fastpow(a, d, p);
    if (x == 1 || x == p - 1) continue;
    rep(i, 1, r) {
      x = mul(x, x, p);
      if (x == p - 1) break;
    }
    if (x != p - 1) return false;
  }
  return true;
}
ll f(ll x, ll c, ll mod) { return (mul(x, x, mod) + c) % mod; }
ll pollard_rho(ll x) {
  ll c = rand() % (n - 1) + 1;
  ll s = 0, t = 0, val = 1;
  for (ll goal = 1;; goal <<= 1, s = t, val = 1) {
    rep(step, 1, goal) {
      t = f(t, c, x);
      val = mul(val, abs(t - s), x);
      if (!val) return x;
      if (step % 127 == 0) {
        ll d = gcd(val, x);
        if (d > 1) return d;
      }
    }
    ll d = gcd(val, x);
    if (d > 1) return d;
  }
}
void fac(ll n) {
  if (n < 2) return;
  if (miller_rabin(n)) {
    ans = max(ans, n);
    return;
  }
  ll x = n;
  while (x >= n) x = pollard_rho(n);
  while (n % x == 0) n /= x;
  fac(x), fac(n);
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  cin >> t;
  while (t--) {
    srand((unsigned)time(0));
    cin >> n;
    ans = 0;
    fac(n);
    if (ans == n)
      cout << "Prime\n";
    else
      cout << ans << endl;
  }
  return 0;
}